package com.gxc.string;

/**
 * 给定一个字符串str，求最长的回文子串。注意区分子序列和子串的不同
 *
 * 解法：
 * dp
 * dp[i][j] i<=j   表示string i ...j 是否是回文
 * dp[i-1][j+1] = dp[i][j] + string[i-1]==string[j+1]
 * dp[i][i] 单字符 肯定是回文
 */
public class LongestPalindromeSubstring {

    public static void main(String[] args) {
        String str = "cbaabcd";
        System.out.println(str.substring(0, 6));

        System.out.println(process(str));
        System.out.println(processStr(str));
    }

    public static int process(String str) {
        char[] chars = str.toCharArray();

        boolean[][] dp = new boolean[str.length()][str.length()];

        int max = 0;
        for (int j = 0; j < str.length(); j++) {
            for (int i = 0; i < str.length(); i++) {
                //确保 i<=j
                if (i>j) break;
                //dp[i][i] = true;
                if (i == j) {
                    dp[i][j] = true;
                    max = Math.max(max, j-i+1);
                }
                //只有两字符的特殊情况处理
                else if (i+1 == j) {
                    if (chars[i] == chars[j]) {
                        dp[i][j] = true;
                        max = Math.max(max, j-i+1);
                    }
                    else dp[i][j] = false;
                } else {
                    if (chars[i] != chars[j]) {
                        dp[i][j] = false;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                        if (dp[i][j]) max = Math.max(max, j-i+1);
                    }
                }
            }
        }

        return max;
    }

    public static String processStr(String str) {
        char[] chars = str.toCharArray();

        boolean[][] dp = new boolean[str.length()][str.length()];

        int max = 0;
        int loc = 0;
        for (int j = 0; j < str.length(); j++) {
            for (int i = 0; i < str.length(); i++) {
                //确保 i<=j
                if (i>j) break;
                //dp[i][i] = true;
                if (i == j) {
                    dp[i][j] = true;
                    max = Math.max(max, j-i+1);
                }
                //只有两字符的特殊情况处理
                else if (i+1 == j) {
                    if (chars[i] == chars[j]) {
                        dp[i][j] = true;
                        max = Math.max(max, j-i+1);
                    }
                    else dp[i][j] = false;
                } else {
                    if (chars[i] != chars[j]) {
                        dp[i][j] = false;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                        if (j-i+1 > max && dp[i][j]) {
                            max = j-i+1;
                            loc = i;
                        }
                    }
                }
            }
        }

        return str.substring(loc, loc+max);
    }

}
